アルゴリズムイントロダクション 第4版 第1巻

https://gyazo.com/3158a26b05aff206095c4f2b60530308

練習問題

1.1-1:ソートを必要とする実社会の例を説明せよ。また、2点間の最短距離を見つけることを必要とする例を説明せよ

ソート

図書館の書籍を本棚に戻す作業

2点間

乗り換え案内

1.1-2：実社会の枠組みの中で用いられる計算速度以外の尺度をあげよ

順番、パフォーマンス、関係

メモリ使用量、実装の複雑さとかだろうと考えたのでこれで

電力とか帯域、正確性もありそう

1.1-3：これまで見たことがあるデータ構造について長所と欠点を述べよ

配列

長所：indexによって管理され番号を指定すればその番号のデータを即座に取り出すことができる

欠点：欲しい情報がある場合にindexを最初から数えて合致するまで探索しないとたどり着けない。挿入や削除したらひとつずつズラさないといけない

相違点は最短路問題では2点間のルートの中ですべてを辿らなくてもよい。巡回セールスパーソン問題はすべての地点必ず通る必要がある。

2点間の最短距離を求めることに関しては類似

近似解でも十分に意味があるのは配送ルートの件

最適解はパスワードのロジック？暗号鍵などの技術？

1.1-6問題を解く時に必要な入力がすべて揃っている場合もあれば、入力が前もってすべては利用できず、後から到着する場合もあるような実社会の問題を示せ

病院の緊急救命室でどの患者を先に診察するか他の患者が今後来るかやその患者にどのような処置が必要であるかも知らずに決定しないといけない

1.2-1 アプリケーションでアルゴリズムが必要になるものの例を挙げ必要ちとされるアルゴリズムの機能を議論せよ

この本の例でもあがっていたけどある場所からある場所までの旅行の計画を手助けしてくれるアプリケーション

ルートの検索とか地図の表示、住所の習得など様々なアルゴリズムが必要

12.2同じコンピューター上で挿入ソートとマージソートの実装を比較する。サイズnの入力に対して挿入ソートの実行は8mの2乗ステップかかり一方マージソートは64nlgnステップかかるとする挿入ソートがマージソートにまさるnの値を調べよ

8nで割る

8/n​<lgn

のように変形したらnに代入していき8/nの数がlg⁡nより下回ったらそこが閾値になる

1.2-3同じコンピュータ上で実行時間が100m2のアルゴリズムが実行時間が2n乗のアルゴリズムより高速に実行できる最小のnを求めよ

さっきと同じ考え方で代入していく